﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;

namespace CombinatorialObjects
{
    /// <summary>
    /// A class to generate permutations. All operations are in situ. That is, they modify the current instance instead of returnig
    /// a modyfied copy.
    /// </summary>
    /// <remarks>
    /// <para>
    /// This class can generate any sequence of permutation of order <see cref="Order"/>.
    /// The <see cref="MoveNext()"/> method returns the next permutation, while
    /// <see cref="GetSuccessors"/> can be used to iterates all the rest of the permutations.
    /// </para>
    /// <para>
    /// The permutation can be applied to an array using <see cref="ApplyTo&lt;T&gt;"/>, it can also
    /// be inverted using <see cref="Inverse"/>.
    /// </para>
    /// <para>
    /// This class was extracted from
    /// <a href="http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnnetsec/html/permutations.asp">
    /// <em>Using Permutations in .NET for Improved Systems Security</em> by
    /// Dr. James McCaffrey.
    /// </a>
    /// </para>
    /// </remarks>
    public class Permutation : ICloneable, IEnumerator<Permutation>, IEnumerable<Permutation>, IEquatable<Permutation>
    {
        private readonly int[] data;
        private readonly int order;

        #region Constructors

        /// <summary>
        /// Creates a new idenity permutation
        /// </summary>
        /// <param name="n">
        /// order of the new permutation
        /// </param>
        public Permutation(int n)
        {
            if (n <= 0)
                throw new ArgumentOutOfRangeException("n", "n cannot be negative or zero");
            order = n;
            data = new int[order];
            //BitConverter.
            MakeIdentity();
        }

        /// <summary>
        /// Turns the current permutation into identity.
        /// </summary>
        public void MakeIdentity()
        {
            for (int i = 0; i < order; ++i)
                data[i] = i;
        }
        /// <summary>
        /// Performs a swap transition (i,j).
        /// </summary>
        public void Swap(int i, int j)
        {
            int temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
        /// <summary>
        /// Finds elements a and b and then swaps them.
        /// </summary>
        public void SwapValues(int a, int b)
        {
            if (a < 0 || a >= order)
                throw new ArgumentOutOfRangeException("a");
            if (b < 0 || b >= order)
                throw new ArgumentOutOfRangeException("b");
            int indexA = 0, indexB = 0;
            bool oneOfThem = false;
            // find a and b
            for (int i = 0; i < order; i++)
            {
                if (data[i] == a)
                {
                    indexA = i;
                    if (oneOfThem) break;
                    oneOfThem = true;
                }
                else if (data[i] == b){
                    indexB = i;
                    if (oneOfThem) break;
                    oneOfThem = true;
                }
            }
            // perform swap.
            Swap(indexA, indexB);
        }
        /// <summary>
        /// Removes i-th element and inserts it before the former j-th element.
        /// </summary>
        /// <param name="i"></param>
        /// <param name="j"></param>
        public void Insert(int i, int j)
        {
            int elem = data[i];
            for (int k = i + 1; k <= j; k++)
                data[k - 1] = data[k];
            data[j] = elem;
        }
        /// <summary>
        /// Creates the <paramref name="k"/>-th permutation of
        /// order <paramref name="n"/>.
        /// </summary>
        /// <param name="n"></param>
        /// <param name="k"></param>
        public Permutation(int n, int k)
        {
            if (n <= 0)
                throw new ArgumentOutOfRangeException("n", "n cannot be negative or zero");
            if (k <= 0)
                throw new ArgumentOutOfRangeException("k", "k cannot be negative or zero");

            data = new int[n];
            order = data.Length;

            // Step #1 - Find factoradic of k
            var factoradic = new int[n];

            for (int j = 1; j <= n; ++j)
            {
                factoradic[n - j] = Math.DivRem(k, j, out k);
            }

            // Step #2 - Convert factoradic to permuatation
            var temp = new int[n];

            for (int i = 0; i < n; ++i)
            {
                temp[i] = ++factoradic[i];
            }

            data[n - 1] = 1; // right-most element is set to 1.

            for (int i = n - 2; i >= 0; --i)
            {
                data[i] = temp[i];
                for (int j = i + 1; j < n; ++j)
                {
                    if (data[j] >= data[i])
                        ++data[j];
                }
            }
            for (int i = 0; i < n; ++i) // put in 0-based form
            {
                --data[i];
            }
        } // Permutation(n,k)

        private Permutation(int[] a)
        {
            if (a.Length == 0)
                throw new ArgumentException("Order cannot be zero");
            data = new int[a.Length];
            a.CopyTo(data, 0);
            order = a.Length;

            CheckPermutation();
        }

        #endregion
        public int this[int index]
        {
            get { return data[index]; }
            set
            {
                if (value < 0 || value >= order)
                    throw new Exception("Value out of range."); // value out of range
                int j;
                if ((j = Array.FindIndex(data, i => i == value)) != -1)
                    throw new Exception("Duplicate value at index " + j); // value out of range

                data[index] = value;
            }
        }
        public void Set(int[] array)
        {
            if (array.Length != order)
                throw new Exception("Array.Length is not equal to the Order");
            var checks = new bool[data.Length];
            for (int i = 0; i < order; ++i)
            {
                if (array[i] < 0 || array[i] >= order)
                    throw new Exception("Value out of range at index " + i); // value out of range

                if (checks[array[i]])
                    throw new Exception("Duplicate value at index " + i); // value out of range
                checks[array[i]] = true;
            }
            for (int i = 0; i < order; i++)
            {
                data[i] = array[i];
            }
        }
        public bool StartsWith(params int[] beginning)
        {
            int length = beginning.Length;
            for (int i = 0; i < order && i < length; i++)
            {
                if (data[i] != beginning[i])
                    return false;
            }
            return true;
        }
        /// <summary>
        /// Moves to the first
        /// </summary>
        /// <param name="beginning"></param>
        /// <param name="order"></param>
        public void First(int[] beginning, int order)
        {
            var check = new bool[order];
            for (int i = 0; i < beginning.Length; i++)
            {
                check[beginning[i]] = true;
                data[i] = beginning[i];
            }
            int checkI = 0;
            for (int i = beginning.Length; i < order; i++)
            {
                while (check[checkI])
                    checkI++;
                data[i] = checkI;
                checkI++;
            }
        }
        public void MoveNext(int[] beginning, int order)
        {
            var check = new bool[order];
            for (int i = 0; i < beginning.Length; i++)
            {
                check[beginning[i]] = true;
                data[i] = beginning[i];
            }
            int checkI = 0;
            for (int i = order - 1; i >= beginning.Length; i--)
            {
                while (check[checkI])
                    checkI++;
                data[i] = checkI;
                checkI++;
            }

        }
        /// <summary>
        /// Moves to the last permutation while preserving the current permutation up to the specified index.
        /// This means that level's item will be increased on the next MoveNext call.
        /// </summary>
        /// <example>
        /// [235 041] -> last(2) -> [235 410]
        /// </example>
        public unsafe void MoveToLastInLevel(int level)
        {
            if (level < 0 || level >= order) // if level == order-1, then there is nothing to skip.
                throw new ArgumentOutOfRangeException("level");
            // In this case, it is always the last perm
            if (level == order - 1)
                return;
            bool* check = stackalloc bool[order];
            //; = new bool[order];
            // Fill the check table.
            fixed (int* dataFix = data)
            {
                int* dataPtr = dataFix;
                for (int i = 0; i <= level; i++, dataPtr++)
                    *(check + *dataPtr) = true;
            }

            // Fill the rest.
            fixed (int* dataFix = data)
            {
                int* dataPtr = dataFix + order - 1;
                bool* checkPtr = check;
                int checkI = 0;
                for (int i = order - 1; i > level; i--, checkPtr++, dataPtr--, checkI++)
                {
                    while (*checkPtr)
                    {
                        checkPtr++;
                        checkI++;
                    }
                    *dataPtr = checkI; // checkI;
                }
            }
            //CheckPermutation();
        }
        /// <summary>
        /// Performs a Knuth Shuffle operation on this permutation.
        /// </summary>
        public void Randomize(Random generator)
        {
            for (int i = 0; i < order; i++)
            {
                int swap = generator.Next(order - 1);
                if (swap >= i)
                    swap++;
                Swap(i, swap);
            }
        }
        /// <summary>
        /// Gets the order of the permutation
        /// </summary>
        /// <value></value>
        public int Order
        {
            get { return order; }
        }

        /// <summary>
        /// Checks that the permutation is correct
        /// </summary>
        public void CheckPermutation()
        {
            if (data.Length != order)
                throw new Exception("Data.Length is not equal to the Order");

            var checks = new bool[data.Length];
            for (int i = 0; i < order; ++i)
            {
                if (data[i] < 0 || data[i] >= order)
                    throw new Exception("Value out of range at index " + i); // value out of range

                if (checks[data[i]])
                    throw new Exception("Duplicate value at index " + i); // value out of range
                checks[data[i]] = true;
            }
        }

        public IEnumerator<Permutation> GetEnumerator()
        {
            return this;
        }

        public bool Equals(Permutation other)
        {
            if (other.order != order)
                return false;
            for (int i = 0; i < other.order; i++)
                if (data[i] != other.data[i])
                    return false;
            return true;
        }


        /// <summary>
        /// Converts the permutation to a string representation.
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            var sb = new StringWriter();
            sb.Write("(");
            for (int i = 0; i < order; ++i)
            {
                sb.Write("{0} ", data[i]);
            }
            sb.Write(")");

            return sb.ToString();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public void Dispose()
        {
        }

        object ICloneable.Clone()
        {
            return new Permutation(data);
        }
        public Permutation Clone()
        {
            return new Permutation(data);
        }

        /// <summary>
        /// Applis the permutation to the array 
        /// </summary>
        /// <param name="arr">
        /// A <see cref="object"/> array of Length equal 
        /// to <see cref="Order"/>.</param>
        /// <returns>
        /// A new array containing the permutated element of <paramref name="arr"/>
        /// </returns>
        public unsafe T[] ApplyTo<T>(T[] arr)
        {
            if (arr.Length != order)
                throw new ArgumentException("array Length is equal to the permutation order");

            var result = new T[arr.Length];
            fixed (int* dataFix = data)
            {
                int* dataPtr = dataFix;
                for (int i = 0; i < result.Length; ++i, dataPtr++)
                {
                    result[i] = arr[*dataPtr];
                }
            }
            return result;
        }

        /// <summary>
        /// Reverses the permutation, ex [123]->[321]
        /// </summary>
        /// <returns></returns>
        public void Reverse()
        {
            for (int i = 0; i < order / 2; ++i)
                data.Swap(i, order - i - 1);
        }
        
        /// <summary>
        /// Inverses the permutation, ex [1423]->[1342]
        /// </summary>
        /// <returns></returns>
        public unsafe void Inverse()
        {
            int* inversed = stackalloc int[order];
            for (int i = 0; i < order; ++i)
                inversed[data[i]] = i;
            for (int i = 0; i < order; i++)
                data[i] = inversed[i];
        }

        /// <summary>
        /// Moves the current permutation to the next permutation in lexicographic order.
        /// </summary>
        public bool MoveNext()
        {
            /*for (int k = 0; k < result.order; ++k) // Step #0 - copy current data into result
            {
                result.data[k] = data[k];
            }*/

            int left = order - 2;
            while ((data[left] > data[left + 1]) && (left >= 1))
            {
                --left;
            }
            if ((left == 0) && (data[left] > data[left + 1]))
                return false;

            int right = order - 1;
            while (data[left] > data[right])
            {
                --right;
            }

            int temp = data[left]; // Step #3 - swap [left] and [right]
            data[left] = data[right];
            data[right] = temp;


            int i = left + 1; // Step #4 - order the tail
            int j = order - 1;

            while (i < j)
            {
                temp = data[i];
                data[i++] = data[j];
                data[j--] = temp;
            }

            return true;
        }

        /// <summary>
        /// Gets an enumerable collection of <see cref="Permutation"/> by modifying the current instance.
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<Permutation> GetPermutations(int order)
        {
            var permutation = new Permutation(order);
            do
            {
                yield return permutation;
            } while (permutation.MoveNext());
        }
        /// <summary>
        /// Gets an enumerable collection of <see cref="Permutation"/> by modifying the current instance..
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<T[]> GetPermutations<T>(T[] array)
        {
            var permutation = new Permutation(array.Length);
            do
                yield return permutation.ApplyTo(array);
            while (permutation.MoveNext());
        }
        /// <summary>
        /// Gets an enumerable collection of <see cref="Permutation"/> successors.
        /// </summary>
        /// <returns></returns>
        public IEnumerable<Permutation> GetSuccessors()
        {
            Permutation permutation = this;
            while (permutation.MoveNext())
                yield return permutation;
        }


        public bool IsABeforeB(int a, int b)
        {
            bool wasA = false;
            for (int i = 0; i < order; i++)
            {
                if (data[i] == a)
                    wasA = true;
                if (data[i] == b)
                    return wasA;
            }
            return false;
        }
        /// <summary>
        /// Sets the enumerator to its initial position, which is before the first element in the collection.
        /// </summary>
        public void Reset()
        {
            MakeIdentity();
        }

        /// <summary>
        /// Gets the current instance of Permutation, which is modyfied on each iteration. (All operations are performed in-place,
        /// by modifying the current instance.)
        /// </summary>
        public Permutation Current
        {
            get { return this; }
        }

        object IEnumerator.Current
        {
            get { return Current; }
        }

        public int[] DataUnsafe
        {
            get { return data; }
        }

        public void Set(Permutation permutation)
        {
            Set(permutation.data);
        }
    }
}